The present invention relates generally to coordination amongst execution sequences in a multiprocessor, and more particularly, to techniques for coordinating access to shared data and pointer encodings.
Use (at runtime) of an automatic dynamic memory management facility, e.g., a garbage collector (GC), can greatly simplify the design of a sequential implementation of a data structure or software mechanism by largely relieving the programmer of the burden of determining when memory can (or should) be deallocated. Moreover, by assuming the existence of an automatic dynamic memory management facility or garbage collector, certain additional complexities of concurrent data structures and software can also be avoided. In particular, it is often possible to defer to the garbage collector the significant additional complexity of coordinating deallocation of memory with potential concurrent accesses thereto.
Furthermore, concurrent data structure implementations and/or software mechanisms for an execution environment that provides garbage collection can (in essence) benefit from a free solution to the so-called ABA problem. In general, the ABA problem arises when a data system fails to detect that a value changes (e.g., from A to B) and then changes back to its original value (i.e., A). For example, if a compare-and-swap-type operation (e.g., a CAS or DCAS operation) is about to operate on a pointer and the object to which it points is freed and then reallocated, then it is possible for the CAS or DCAS to succeed even though it should fail. In a proper implementation, this possibility should be prevented by ensuring that an object is not freed while an execution thread has pointers to it. Garbage collector implementations typically ensure such behavior, e.g., by stopping a thread and inspecting its registers and stack for pointers. However, in the absence of a garbage collector, responsibility for handling the ABA problem generally falls to the concurrent data structure implementation itself.
For these and other reasons, deferring complexity to a runtime garbage collection facility can be quite attractive. However, such a facility is not always available or practical. For example, many common programming and execution environments do not support garbage collection. Second, even those environments that do support garbage collection often employ excessive synchronization, such as locking and/or stop-the-world mechanisms, which impair scalability and may be impractical for certain applications. Worse still, some software systems (notably implementations of a garbage collector itself) simply cannot defer the complexity to a runtime garbage collection system. For example, concurrent shared object implementations that depend on the existence of a garbage collection facility are generally not suitable for use in the implementation of the garbage collector itself. Accordingly, for some software systems, concurrent data structures and mechanisms, direct solutions to the difficult problem of coordinating concurrent access to shared, storage are necessary or desirable.
The difficulty of achieving correct solutions should not be underestimated, particularly for dynamically-sizable shared data structures. Indeed, despite the fact that use of locks in concurrent programs gives rise to a host of problems including deadlock, starvation and intolerance to thread failure, many concurrent or cooperative software systems in use today employ lock-based techniques.
Significant research attention has been paid to “nonblocking” synchronization, i.e., synchronization that does not depend on locks. Unfortunately, both the design and verification of nonblocking algorithms are very challenging. Accordingly, much of the early work in this area has focused on what can be achieved in principle, yet has yielded relatively few practical results. In particular, work on nonblocking shared data structures has typically ignored the important issues of managing memory for dynamic-sized shared data structures. Indeed, much of the work that has been done before a few years ago is either incorrect (i.e., inoperative despite its surface appeal) or has serious drawbacks.
In view of the above, nonblocking structures and techniques are desired that would allow programmers to exploit the advantages of a garbage collected execution environment in the design of data structure implementations despite the absence of a garbage collection facility.